public class LinkedList implements List {
    private class Node {
	Object item;
	Node next;
	Node prev;
    }
    private Node head;
    private Node tail;
    private int size;

    public LinkedList() {
	clear();
    }
    public int size() {
	return size;
    }
    public void clear() {
	size = 0;
	head = new Node();
	tail = new Node();
	head.next = tail;
	tail.prev = head;
    }
    public boolean isEmpty() {
	return size() == 0;
    }

    public boolean add(Object x) {
	Node tmp = new Node();
	tmp.item = x;
	tmp.prev = tail.prev;
	tmp.next = tail;
	tail.prev.next = tmp;
	tail.prev = tmp;
	size++;
	return true;
    }

    private Node find(Object x) {
	for (Node n = head.next; n != tail; n = n.next)
	    if (n.item.equals(x))
		return n;
	return null;
    }
    public boolean remove(Object x) {
	Node n = find(x);
	if (n != null) {
	    n.next.prev = n.prev;
	    n.prev.next = n.next;
	    n.next = null;
	    n.prev = null;
	    size--;
	}
	return n != null;
    }
    public boolean contains(Object x) {
	return find(x) != null;
    }

    public Object[] toArray() {
	Object[] array = new Object[size()];
	int i = 0;
	for (Node n = head.next; n != tail; n = n.next)
	    array[i++] = n.item;
	return array;
    }
    public String toString() {
	String s = "[";
	for (Node n = head.next; n != tail; n = n.next) {
	    s += n.item;
	    if (n.next != tail)
		s += ", ";
	}
	return s + "]";
    }

    private Node findPosition(int index) {
	Node n = head.next;
	for (int i = 0; i < index; i++)
	    n = n.next;
	return n;
    }
    public Object get(int index) {
	Node n = findPosition(index);
	return n.item;
    }
    public Object set(int index, Object element) {
	Node n = findPosition(index);
	Object item = n.item;
	n.item = element;
	return item;
    }

    public Iterator iterator() {
	return new LinkedListIterator();
    }
    private class LinkedListIterator implements Iterator {
	private Node current;
	LinkedListIterator() {
	    current = head.next;
	}
	public boolean hasNext() {
	    return current != tail;
	}
	public Object next() {
	    Object item = current.item;
	    current = current.next;
	    return item;
	}
    }
}